# -*- coding: utf-8 -*-            
# @Time : 2022/11/23 22:10
# @Author  : lining
# @FileName: 有环链表找环的第一个节点.py
"""
https://leetcode.cn/problems/linked-list-cycle-ii/
解题思路：没环的个数a,有环的元素个数b，总个数a+b
fast的速度是slow的2倍
fast = 2slow
每次相遇，fast都比slow多走n个环，即nb
fast - slow = nb
得  slow = nb
即：两个指针相遇后，满指针只需要再走a步就是环的 第一个节点
"""

class Node():
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class Solution():
    def detectCycle(self, head):
        """
        边界问题：如果没有环，那么必定fast先取到最后一个，fast可能取到none，也可能取到none的后一个
        :param head: 头结点，Node类型
        :return:
        """
        fast = head
        slow = head
        # 没有环不是fast是none就是fast.next是none
        while True:
            if fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if fast is slow:
                    print('有环')
                    break
                continue
            return
        fast = head
        while fast is not slow:
            fast = fast.next
            slow = slow.next
        return fast


a = Node(1)
b = Node(2)
a.next = b
b.next = a
x = Solution().detectCycle(a)
print(x)
